package list

// Problem Definition: https://www.nowcoder.com/practice/ef1f53ef31ca408cada5093c8780f44b?tpId=117&tqId=37776&rp=1

func reorderArray(nums []int) []int {
	if len(nums) == 0 {
		return nums
	}

	var even, odd []int
	for i := range nums {
		if nums[i]%2 == 0 {
			even = append(even, nums[i])
		} else {
			odd = append(odd, nums[i])
		}
	}

	return append(odd, even...)
}

func reorderArray1(nums []int) []int {
	i := 0
	for j := 0; j < len(nums); j++ {
		if nums[j]%2 == 0 {
			continue
		}

		tmp := nums[j]
		for k := j - 1; k >= i; k-- {
			nums[k+1] = nums[k]
		}
		nums[i] = tmp
		i++
	}

	return nums
}
